package 二叉树.BinaryTreeDepthTravel;

import 二叉树.BinaryTreeTemplate;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


/**
 * 此文件专门用于二叉树的深度遍历-迭代法
 * 说明:
 * A 迭代具有特殊性 ——统一迭代、一般迭代法、遍历结果反转法
 * B 以下代码按照遍历的顺序划分 123 第二位数字123表示是统一迭代迭代还是迭代
 *
 * A对于统一迭代
 *    中左右 左中右 左右中 -基于栈操作
 *
 * B对于一般迭代
 *  1对于 中左右    -基于栈操作
 *    由于需要操作一次需要操作两个节点
 *
 *  2对于 左中右 左右中   -基于节点操作
 *    每个节点都是树结构 于是允许整个操作只通过一个第三节点进行换树操作
 *    如何理解开头Node和他的.left的关系-入栈是基于层次的说明
 *
 * 一般迭代 peek一次 pop一次
 * 统一迭代 pop两次
 */

public class BinaryTreeDepthTravelForIteration {
    /**
     *         1
     *       /   \
     *      2     3
     *     / \   / \
     *    4   5 6   7
     */
    BinaryTreeTemplate tree = BinaryTreeTemplate.createCompleteBinaryTree();

    /**-----------------------1中左右 统一迭代--------------------------**/
    public List<Integer> front11() {
        List<Integer> result = new ArrayList<>();
        Stack<BinaryTreeTemplate> stack = new Stack<>();
        if (this.tree != null) stack.push(this.tree);
        while (!stack.isEmpty()) {
            BinaryTreeTemplate levelNode = stack.pop();//本层次节点
            if (levelNode != null) {

                if (levelNode.right != null){ // 右
                    stack.push(levelNode.right);
                }

                if (levelNode.left != null){ // 左
                    stack.push(levelNode.left);
                }

                stack.push(levelNode);
                stack.push(null); //下层次根节点处理完毕

            }else {
                Integer value = stack.pop().value;
                result.add(value);
            }
        }
        return result;
    }
    /**-----------------------1中左右 一般迭代--------------------------**/
    public List<Integer> front12() {
        List<Integer> result = new ArrayList<>();
        Stack<BinaryTreeTemplate> stack = new Stack<>();
        if (this.tree != null) stack.push(this.tree);
        while (!stack.isEmpty()) {

            BinaryTreeTemplate levelNode = stack.pop();
            result.add(levelNode.value);// 当前层次节点<树的根节点>

            if (levelNode.right != null){ // 右
                stack.push(levelNode.right);
            }

            if (levelNode.left != null){ // 左
                stack.push(levelNode.left);
            }

        }
        return result;
    }


    /**-----------------------2左中右 统一迭代--------------------------**/
    public List<Integer> middle21(){
        List<Integer> result = new ArrayList<>();
        Stack<BinaryTreeTemplate> stack = new Stack<>();
        if (this.tree != null) stack.push(this.tree);
        while (!stack.isEmpty()) {
            BinaryTreeTemplate levelNode = stack.pop();// 当前层次节点<树的根节点>
            if (levelNode != null) {

                if (levelNode.right != null){ // 右
                    stack.push(levelNode.right);
                }

                stack.push(levelNode);
                stack.push(null);// 下层次根节点处理完毕

                if (levelNode.left != null){ // 左
                    stack.push(levelNode.left);
                }

            }
            else {
                Integer value = stack.pop().value;
                result.add(value);
            }
        }
        return result;
    }
    /**-----------------------2左中右 一般迭代--------------------------**/
    public List<Integer> middle22(){
        BinaryTreeTemplate operationNode = this.tree;

        List<Integer> result = new ArrayList<>();
        Stack<BinaryTreeTemplate> stack = new Stack<>();

        while (operationNode != null || !stack.isEmpty()) {
            while (operationNode != null) {
                stack.push(operationNode);
                operationNode = operationNode.left;
            }

            BinaryTreeTemplate middle = stack.pop();
            result.add(middle.value);

            if (middle.right != null) {
                operationNode = middle.right;
            }
        }
        return result;
    }



    // 用于思考 入栈时元素的含义 condition2
    //——指本层次的标记 所以任何一颗树operationNode入栈 而不是通过.left进行左入到底操作
    public List<Integer> middleAbandon(){
        BinaryTreeTemplate operationNode = this.tree;

        List<Integer> result = new ArrayList<>();
        Stack<BinaryTreeTemplate> stack = new Stack<>();

        while (operationNode != null || !stack.isEmpty()) {
            stack.push(operationNode);
            while (operationNode.left != null) {
                stack.push(operationNode.left);// 左到底-驱动器
                operationNode = operationNode.left;
            }

            // 作为树根处理当前层次 (此时就算是左到底起手 处理逻辑也是一致的)
            //先作为中输出
            BinaryTreeTemplate pop = stack.pop();
            result.add(pop.value);

            //处理右子树
//            if (pop.right != null) {
//                stack.push(operationNode = pop.right);
//            } —— 应该明白一个道理 基于元素(树)而不是栈
            operationNode = pop.right;
        }
        return result;
    }



    /**----------------------3左右中 统一迭代--------------------------**/
    public List<Integer> behind31(){
        List<Integer> result = new ArrayList<>();
        Stack<BinaryTreeTemplate> stack = new Stack<>();
        if (this.tree != null) stack.push(this.tree);
        while (!stack.isEmpty()) {
            BinaryTreeTemplate levelNode = stack.pop();// 当前层次节点<树的根节点>
            if (levelNode != null) {
                stack.push(levelNode);
                stack.push(null);// 下层次根节点处理完毕

                if (levelNode.right != null) stack.push(levelNode.right);// 右
                if (levelNode.left != null) stack.push(levelNode.left);// 左
            }else {
                Integer value = stack.pop().value;
                result.add(value);
            }
        }
        return result;
    }
    /**----------------------3左右中 一般迭代--------------------------**/
    public List<Integer> behind32(){
        List<Integer> result = new ArrayList<>();
        Stack<BinaryTreeTemplate> stack = new Stack<>();

        BinaryTreeTemplate operation = this.tree;  // 迭代与起始
        BinaryTreeTemplate popNode = null;  // 记录上一个出栈的

        while (this.tree != null || stack != null) {
            while (operation != null) {
                stack.push(operation);
                operation = operation.left;
            }
        }

        //开始倒回
        BinaryTreeTemplate peek = stack.peek();

        if (peek != null && peek.right != null) {

        }



        return null;
    }

    //遗弃版 用于逻辑分析 condition1
    // 理清出操作是基于节点对象来的 本质来说就是基于此换树操作(那么入栈说明是condition2层次关系)
    public List<Integer> behindAbandon(){
        List<Integer> result = new ArrayList<>();
        Stack<BinaryTreeTemplate> stack = new Stack<>();
        if (this.tree != null) stack.push(this.tree);

        while (!stack.isEmpty() && this.tree != null) { // 起始和 下一步
            //左到底
            BinaryTreeTemplate downNode = stack.peek();
            while (downNode != null) { // 迭代问题! -左到底的.left-> null 但是这里的主角是栈为了入栈没啥意义了
                stack.push(downNode); // 到底
                downNode = downNode.left;
            }

            BinaryTreeTemplate doNode = stack.pop(); // 开始处理
            result.add(doNode.value);

            //判断右边是否完成
            if (doNode != stack.peek().right && stack.peek().right != null) { // != null的原因:对象报错 对象.right()不允许
                //右子树入栈                                                   // 上面进行了pop(4) 此时其实是2.right 那么!=null是指5!= 逻辑漏洞
                stack.push(doNode.right);
            }
        }
        return result;
    }



    public List<Integer> behindReserve(BinaryTreeTemplate root){
        return null;
    }
}
